/**
 * 双向链表
 */

class Node{
    constructor(element){

        this.element = element // 数据
        this.previous = null // 指向上一个
        this.next = null // 指向下一个
    }
}

class LinkList {
    constructor() {
        this.head = null
        this.last = null
        this.size = 0
    }

    //以字符串形式显示链表元素
    toString () {
        var currNode = this.head
        var string = '['
       for(let i=0;i<this.size;i++){

            string += currNode.element + ','
            currNode = currNode.next
        }
        string = string.slice(0, string.length - 1)+']'
        return string
    }

    // 追加元素为新节点到链表最后
    append(element){
        let newNode  = new Node(element)
        if(this.head == null) {
            this.head = newNode
            this.last = newNode
        }else {
            //注意：由于last和head都指向同一个节点对象（引用类型数据），故修改last的属性head会跟着变化，
            // 除非下面的第4步last重新整体赋值为另外一个对象，再操作last的属性不改变head
            // 1.将新节点newNode指向上一个的指针指向原来链表最后一个节点last
            newNode.previous = this.last
            // 2.将新节点newNode指向下一个的指针指向null
            newNode.next = null
            // 3.将原来链表最后一个节点last指向下一个的指针指向新节点newNode
            this.last.next = newNode
            // 4.最后设置新节点newNode为链表最后一个节点
            this.last = newNode
        }
        this.size++
    }

    //返回索引对应的节点的值
    get(index){
        let tempNode = null;
        if(index<0 || index>this.size-1) {
            throw  "index 不合法...."+index
        }
        // 优化查找,小于size/2
        let tempSize =( this.size>>1)
        if(index<=tempSize) {
            tempNode = this.head
            for(let i=0;i<index;i++) {
                tempNode = tempNode.next
            }
        }else {
            tempNode = this.last
            for(let j=this.size-1;j>index;j--) {
                tempNode = tempNode.previous
            }
        }
        return tempNode.element
    }

    // 返回该元素的节点
    getNode(element){
        let currNode = this.head
        for(let i=0;i<this.size;i++) {
            if(currNode.element === element){
                return currNode
            }
            currNode  = currNode.next
        }
        return null
    }

    // 删除一个节点，根据元素element删除
    remove(element){
        let currNode = this.getNode(element)
        // 如果element不存在链表则抛出异常
        if( currNode == null ) {
            throw element+"不存在,无法操作！"
        }else {
            let preNode = currNode.previous
            let nextNode = currNode.next
            // 删除第一个节点
            if(currNode===this.head) {
                this.head = nextNode
            }
            // 删除最后一个节点
            else if(currNode===this.last) {
                this.last = preNode
            }
            // 删除其他任意节点
            else{
                preNode.next = nextNode
                nextNode.previous = preNode
            }
            currNode.next = null
            currNode.previous = null
            this.size--
        }

    }
}


let list = new LinkList();
list.append("head");
list.append("1");
list.append("a");
list.append("b");
list.append("c");
console.log(list.toString())
list.remove("head")
list.remove("c")
list.append("f");
console.log(list.toString())
console.log(list.get(3))